package demo3;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSortTest {
    public static void main(String[] args) {
        int[] arr = new int[]{4,2,9,5,1,16,3};
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr,int left,int right) {

        if(left >= right) return;  // 递归结束条件

        int mid = (left+right)/2;  //划分子序列
        mergeSort(arr,left,mid);   //对左侧子序列进行递归排序
        mergeSort(arr,mid+1,right);  //对右侧子序列进行递归排序
        merge(arr, left, mid, right);//合并
    }

    //两路归并算法，两个排好序的子序列合并为一个子序列
    public static void merge(int [] arr,int left,int mid,int right){
        int [] temp=new int[arr.length];//辅助数组
        int p1=left,p2=mid+1,index=left;//p1、p2是检测指针，index是存放指针
        while(p1<=mid && p2<=right) {
            if (arr[p1] <= arr[p2]){
                temp[index] = arr[p1];
                p1++;
            }
            else{
                temp[index]=arr[p2];
                p2++;
            }
            index++;
        }

        //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p1<=mid)
            temp[index++]=arr[p1++];

        //如果第二个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right)
            temp[index++]=arr[p2++];

        //复制回原素组
        for (int i = left; i <=right; i++)
            arr[i]=temp[i];
    }

}
